package a10_动态规划;

import java.util.Scanner;

/**
 * <p>
 * a11_背包理论基础1复习1
 * </p>
 *
 * @author flyduck
 * @since 2025/2/11
 */
public class a11_背包理论基础1复习1 {
    public static void main(String[] args) {
        ///////////////////////////////////////////////
        Scanner scanner = new Scanner(System.in);
        int number = scanner.nextInt();//几个物品
        int totalWeight = scanner.nextInt();//总重量

        int[] weightArray = new int[number];//每个物品的重量
        int[] valueArray = new int[number];//每个物品的价值

        for (int i = 0; i < number; i++) {
            weightArray[i] = scanner.nextInt();
        }

        for (int i = 0; i < number; i++) {
            valueArray[i] = scanner.nextInt();
        }

        ///////////////////////////////////////////////

        //物品  重量  价值
        // 0     1    15
        // 1     3    20
        // 2     4    30

        //重量为4

//        int number = 3;//几个物品
//        int totalWeight = 4;//总重量
//
//        int[] weightArray = new int[]{1,3,4};//每个物品的重量
//        int[] valueArray = new int[]{15,20,30};//每个物品的价值

        //dp[i][j]含义：从0-i个物品挑选随意几个放到总重量为j的背包的最大价值

        //递推公式：
        //不放i：dp[i-1][j]
        //放i：dp[i-1][j-weight[i]] + value[i]
        //dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i])

        //初始化：
        //重量为0：dp[0][0] -> dp[number-1][0] = 0
        //只有第一个物品：dp[0][0] -> dp[0][totalWeight]

        int[][] dp = new int[number][totalWeight + 1];

        //初始化
        for (int i = 0; i < number; i++) {
            dp[i][0] = 0;
        }

        for (int j = 1; j <= totalWeight; j++) {
            if(j >= weightArray[0]){
                dp[0][j] = valueArray[0];
            }
        }

        //遍历
        for (int i = 1; i < number; i++) {
            for (int j = 1; j <= totalWeight; j++) {
                if(j >= weightArray[i]){
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weightArray[i]] + valueArray[i]);
                }else {
                    dp[i][j] =dp[i-1][j];
                }

            }
        }

        System.out.println(dp[number-1][totalWeight]);


    }
}
